package datastructure.graph.有向图;

/**
 * 有向图的可达性
 * @author MaoLin Wang
 * @date 2020/2/2210:44
 */
public class DirectedDFS {
    private boolean[] marked;

    /**
     * 单点可达性
     * 经过此方法，从marked(int v)返回是否存在一条从s到达给定顶点v的有向路径
     * @param digraph
     * @param s
     */
    public DirectedDFS(Digraph digraph, int s) {
        marked=new boolean[digraph.V()];
        dfs(digraph,s);
    }

    /**
     * 多点可达性
     * 是否存在一条从集合中的任意顶点到达给定顶点v的有向路径
     * @param digraph
     * @param sources
     */
    public DirectedDFS(Digraph digraph, Iterable<Integer> sources) {
        marked=new boolean[digraph.V()];
        for (int s:sources){
            if (!marked[s]){
                dfs(digraph,s);
            }
        }

    }

    private void dfs(Digraph digraph, int v) {
        marked[v]=true;
        for (int w:digraph.adj(v)){
            if (!marked[w]){
                dfs(digraph,w);
            }
        }
    }

    public boolean marked(int v){
        return marked[v];
    }

    public static void main(String[] args) {
        Digraph graph=new Digraph(6);
        graph.addEdge(0,2);
        graph.addEdge(0,1);
        graph.addEdge(0,5);
        graph.addEdge(2,1);
        graph.addEdge(2,3);
        graph.addEdge(4,5);

    }

}
